“School of Biological Sciences”

Back to Papers Home
Back to Papers of School of Biological Sciences

Paper   IPM / Biological Sciences / 13237
School of Biological Sciences
  Title:   Enhanced Evolutionary And Heuristic Algorithms For Haplotype Reconstruction Problem Using Minimum Error Correction Model
  Author(s): 
1.  M. Kargar.
2.  H. Poormohammadi.
3.  L. Pirhaji.
4.  M. Sadeghi.
5.  H. Pezeshk.
6.  C. Eslahchi.
  Status:   Published
  Journal: Match
  No.:  2
  Vol.:  62
  Year:  2009
  Pages:   261-274
  Supported by:  IPM
  Abstract:
Construction of two haplotypes from a set of Single Nucleotide Polymorphism (SNP) fragments is referred to as haplotype reconstruction problem. One of the most important computational models for this problem is Minimum Error Correction (MEC). Since MEC is an NP-hard problem, here we propose a heuristic algorithm for haplotype reconstruction problem. The algorithm is Particle Swarm Optimization (PSO) which is an evolutionary algorithm (EA). Evolutionary algorithms are stochastic search algorithms that imitate the natural biological evolution or the social behavior of species. In contrast to MEC model, our algorithm produces results in feasible time and it could be applied to large datasets. Our results suggest that the algorithm has less reconstruction error rate compared to other algorithms. This error is also very close to zero when the algorithm is applied to actual biological data. A comprehensive comparison between PSO and four famous algorithms in the literature is presented. A discussion on input parameters influencing reconstruction error rate is also presented. More info: http://match.pmf.kg.ac.rs/electronic_versions/Match62/n2/match62n2_261-274.pdf

Download TeX format
back to top
scroll left or right